Occasionally during the course of operation of a computer system, the contents of its main memory may become garbled or lost, due to power or transmission line interruption or other system malfunctions. Several techniques have been developed for returning the data structures in the computer memory to a recent consistent state after a failure occurs. In particular, checkpointing is a technique based on the principle of storing and periodically updating an extra copy (complete or incremental with a base) of one or more data structures on memory media having an independent failure mode. A survey of recovery techniques is given by J. S. M. Verhofstad in "Recovery Techniques for Database Systems", Computing Surveys, 10:2, pp. 167-195 (June 1978).
Different checkpointing schemes use different methods to periodically change the "extra" copy of the data structure (usually stored in a disc memory) to take account of changes in the main memory that occurred since the last checkpoint. For example, in a method called "update-in-place", to modify a disc page, a copy of that page is made and the copy is written to another unused disc page in a so-called "undo log". The original page is then modified in situ, hence the name "update in place". To "do" the modification, nothing more need be done; the new page on the undo log (containing the old copy) is later released. On the other hand, to "undo" the modification, the contents of the modified page are replaced with the contents of the page stored on the undo log. Update-in-place is thus biased toward doing modifications, since no further action is needed to keep disc pages after they have been modified. A more complete description of update-in-place is given in an article by J. Gray entitled "Notes on Data Base Operating Systems", in Operating Systems--An Advanced Course, ed. G. Seegmuller, Springer Verlag, pp. 393-481 (1978).
In some circumstances, an alternative checkpointing technique known as shadowing, which is biased toward undoing modifications, is preferred. In shadowing, a copy of a recent consistent state of the data structure is maintained in a read-only status on disc. To modify the contents of a disc page, a copy of that page is modified but then stored in a new page on disc. The original page remains untouched, and is thus called the "shadow". The modification is undone simply by freeing the new page; to "do" the modification, all pointers to the old (shadow) page are changed to point to the new page, and the old page is thereafter freed. Shadowing is described generally in an article by R. A. Lorie in "Physical Integrity in a Large Segmented Database", TODS, 2:1, pp 91-104 (March 1977).
While shadowing has several advantages, its wider acceptance has been hindered by its inability to deal efficiently with a data structure known as a "linked list", which is a series of items (such as memory pages) each of which includes both stored information and a pointer to the address of the next item (page) in the series. In particular, a problem arises when pointers are changed from an old shadow page to a new page, since the pointers are themselves stored on pages which have now changed, and must be updated. Modifications thus propagate, generally resulting in the need to recopy the entire linked list. Such mass recopying obviously decreases system efficiency, and seriously increases the difficulty of implementing a checkpoint by shadowing strategy for failure recovery. Also, while the recopying problem might be alleviated by prepending information accumulated in a second, read/write linked list since the last checkpoint to the original shadow copy of list, this would alter the sequence of the information. In some instances, it is preferable that the new information be added to the end (i.e., appended) of the existing list, to preserve its order.
In view of the foregoing, it is the broad object of the present invention to enable the use of a checkpoint shadowing strategy to recover information lost during a computer memory failure, in instances in which information is stored in the memory in a linked list structure. Specific objects are to permit updating of the read-only shadow copy of the linked list at each checkpoint without recopying the entire linked list, while maintaining the order in which the information is stored in the list.